package 图;

import com.alibaba.fastjson.JSON;

import java.util.*;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-12-25
 **/

public class No802找到最终的安全状态 {

    /**
     * 在有向图中，以某个节点为起始节点，从该点出发，每一步沿着图中的一条有向边行走。
     * 如果到达的节点是终点（即它没有连出的有向边），则停止。
     * 对于一个起始节点，如果从该节点出发，无论每一步选择沿哪条有向边行走，
     * 最后必然在有限步内到达终点，则将该起始节点称作是 安全 的。
     * 返回一个由图中所有安全的起始节点组成的数组作为答案。答案数组中的元素应当按 升序 排列。
     * 该有向图有 n 个节点，按 0 到 n - 1 编号，其中 n 是 graph 的节点数。
     * 图以下述形式给出：graph[i] 是编号 j 节点的一个列表，满足 (i, j) 是图的一条有向边。
     * <p>
     * 示例 1：
     * 输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
     * 输出：[2,4,5,6]
     * 解释：示意图如上。
     * 示例 2：
     * 输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
     * 输出：[4]
     *  
     * 提示：
     * n == graph.length
     * 1 <= n <= 104
     * 0 <= graph[i].length <= n
     * graph[i] 按严格递增顺序排列。
     * 图中可能包含自环。
     * 图中边的数目在范围 [1, 4 * 10^4] 内。
     */

    public List<Integer> eventualSafeNodes(int[][] graph) {

        /**
         * 题目意思就是找到没有环的节点, 根据入度和出度进行判断。
         */

        Info info = new Info(graph.length, 4 * 10 * 10 * 10 * 10);
        for (int i = 0; i < graph.length; i++) {
            for (int j : graph[i]) {
                // 反向加入,因为要反向搜索
                info.add(j, i);
            }
        }

        int[] outDegree = info.outDegree;
        int[] inDegree = info.inDegree;

        // 统计完毕,然后找到所有入度为0的点(反向)
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < outDegree.length; i++) {
            if (inDegree[i] == 0) {
                deque.addLast(i);
            }
        }

        // 入度为0的点,然后吐出
        while (!deque.isEmpty()) {
            // 吐出入度为0的点
            Integer i = deque.removeFirst();
            // 然后再看它指向谁
            int edgeIndex = info.itemEdge[i];
            for (; edgeIndex != -1; edgeIndex = info.nextEdge[edgeIndex]) {
                // 指向此点
                int endItem = info.edgeEnd[edgeIndex];
                // 其入度-1
                inDegree[endItem]--;
                // 入度为0了,就放入
                if (inDegree[endItem] == 0) {
                    deque.addLast(endItem);
                }
            }
        }

        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                result.add(i);
            }
        }

        return result;
    }

    private static class Info {

        // 入度
        public int[] inDegree;
        // 出度
        public int[] outDegree;
        // 当前节点的头边
        public int[] itemEdge;
        // 当前边的下一条边
        public int[] nextEdge;
        // 当前边的终点
        public int[] edgeEnd;
        // 边下标
        public int index;

        public Info(int n, int m) {
            this.itemEdge = new int[n];
            this.nextEdge = new int[m];
            this.edgeEnd = new int[m];
            this.inDegree = new int[n];
            this.outDegree = new int[n];
            Arrays.fill(this.itemEdge, -1);
        }

        public void add(int a, int b) {
            int lastEdge = this.itemEdge[a];
            this.itemEdge[a] = this.index;
            this.nextEdge[this.index] = lastEdge;
            this.edgeEnd[this.index] = b;
            this.outDegree[a]++;
            this.inDegree[b]++;
            this.index++;
        }

    }

    public static void main(String[] args) {
        No802找到最终的安全状态 n = new No802找到最终的安全状态();
        int[][] arr = {{1, 2}, {2, 3}, {5}, {0}, {5}, {}, {}};
        List<Integer> result = n.eventualSafeNodes(arr);
        System.out.println(JSON.toJSONString(result));
    }

}
